DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2023.5

𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots

Authors: Caterina Feletti, Carlo Mereghetti, and Beatrice Palano

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract

We study the Uniform Circle Formation (UCF) problem for a distributed system of n robots which are required to displace on the vertices of a regular n-gon. We consider a well-studied model of autonomous, anonymous, mobile robots that act on the plane through Look-Compute-Move cycles. Moreover, robots are unaware of the cardinality of the system, they are punctiform, completely disoriented, opaque, and luminous. Collisions among robots are not tolerated. In the literature, the UCF problem has been solved for such a model by a deterministic algorithm in the asynchronous mode, using a constant amount of light colors and 𝒪(n) epochs in the worst case. In this paper, we provide an improved algorithm for solving the UCF problem for asynchronous robots, which uses 𝒪(log n) epochs still maintaining a constant amount of colors.

Cite as

Caterina Feletti, Carlo Mereghetti, and Beatrice Palano. 𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.OPODIS.2023.5,
  author =	{Feletti, Caterina and Mereghetti, Carlo and Palano, Beatrice},
  title =	{{𝒪(log\{n\})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.5},
  URN =		{urn:nbn:de:0030-drops-194956},
  doi =		{10.4230/LIPIcs.OPODIS.2023.5},
  annote =	{Keywords: Autonomous mobile robots, Opaque robots, Luminous robots, Pattern formation}
}

Search Results

Documents authored by Feletti, Caterina

𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots

Abstract

Cite as

Thanks for your feedback!

Could not send message